
/********************************** LICENSE ************************************
 *
 * Copyright 2011 Alessandro Carrega
 * email: alessandro.carrega@unige.it
 *
 * This file is part of google_code_jam_2011.
 *
 * google_code_jam_2011 is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * google_code_jam_2011 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with google_code_jam_2011.  If not, see <http://www.gnu.org/licenses/>.
 *
 ********************************* LICENSE ************************************/

#include <iostream>
#include <fstream>
#include <string.h>
#include <string>

inline int index(char c) {
	return c - 'A';
}

int main()
{
	std::ifstream input_file("../input");

	int num_tests;
	input_file >> num_tests;

	int input_index;
	bool char_in_output[26];
	char input_str[101], map_combine[26][26], map_opposed[26];

	int n, tmp_int;
	char tmp_c, tmp_str[4];
	char *ch, *prev_ch;

	for (int i = 1; i <= num_tests; i++)
	{
		memset(input_str, 0, 101);
		memset(char_in_output, 0, 26);
		memset(map_combine, 0, 26*26);
		memset(map_opposed, 0, 26);
		input_index = -1;

		input_file >> tmp_int;
		for (int j = 0; j < tmp_int; j++) {
			input_file >> tmp_str;
			map_combine[index(tmp_str[0])][index(tmp_str[1])] = tmp_str[2];
			map_combine[index(tmp_str[1])][index(tmp_str[0])] = tmp_str[2];
		}

		input_file >> tmp_int;
		for (int j = 0; j < tmp_int; j++) {
			input_file >> tmp_str;
			map_opposed[index(tmp_str[0])] = tmp_str[1];
			map_opposed[index(tmp_str[1])] = tmp_str[0];
		}

		input_file >> n;
		input_file >> input_str[++input_index];
		char_in_output[index(*input_str)] = true;
		for (int j = 1; j < n; j++) {
			prev_ch = input_str + input_index;
			input_file >> input_str[++input_index];
			ch = input_str + input_index;
			char_in_output[index(*ch)] = true;

			//std::cerr << j << "/" << n << " " << std::string(input_str, input_index+1) << " ch: " << *ch << " prev: " << *prev_ch << std::endl;

			tmp_c = map_combine[index(*ch)][index(*prev_ch)];
			if (tmp_c != 0)
			{
				char_in_output[index(tmp_c)] = true;
				char_in_output[index(*ch)] = char_in_output[index(*prev_ch)] = false;

				input_str[--input_index] = tmp_c;
				//std::cerr << j << std::endl;
				if (j == n - 1) break;

				ch = prev_ch;
				prev_ch--;
			}

			tmp_c = map_opposed[index(*ch)];
			//std::cerr << tmp_c << " " << *ch << " " << char_in_output[index(tmp_c)] << std::endl;
			if (tmp_c != 0 && char_in_output[index(tmp_c)])
			{
				input_index = -1;
				if (j == n - 1) break;

				memset(char_in_output, 0, 26);

				input_file >> input_str[++input_index];
				j++;
			}
		}

		input_str[++input_index] = 0;

		std::cout << "Case #" << i << ": [";
		if (input_index > 0) {
			int j;
			for (j = 0; j < input_index - 1; j++) std::cout << input_str[j] << ", ";
			std::cout << input_str[j];
		}
		std::cout << "]" << std::endl;
	}

	input_file.close();
	return 0;
}
